\documentclass[11pt]{article}
\newtheorem{define}{Definition}
%\newcommand{\F}{{\mathbb{F}}}
%\usepackage{psfig}
\usepackage{amsmath,amssymb,amsfonts}
\usepackage{graphicx}
\usepackage{fullpage, color}

\oddsidemargin=0.15in
\evensidemargin=0.15in
\topmargin=-.5in
\textheight=9in
\textwidth=6.25in

\begin{document}
\input{preamble.tex}

\lecture{6}{Sept 6, 2012}{Elena Grigorescu}{Stephanie Oh}

\section*{Testing $\triangle$-freeness}

Today our goal is to finish the proof  that $\triangle$-freeness is testable with a constant number of queries. As we will see, this is an immediate consequence of the $\triangle$-removal lemma stated in the previous lecture. Today we'll  prove the $\triangle$-removal lemma.


\begin{theorem}\label{thm:test3free}
$\triangle$-freeness is testable with a constant number of queries.
\end{theorem}

Recall the $\triangle$-removal lemma.

\begin{lemma}[$\triangle$-removal]\label{3removal}
If $G$ is dense (i.e. $\theta(n^2)$ edges) and is $\epsilon$-far from $\triangle$-free then $G$ contains $\delta(\epsilon)\binom{n}{3}$ triangles where $n$ is the number of vertices in $G$. 
\end{lemma}

Recall that $\epsilon$-far means that $\epsilon\binom{n}{2}$edges need to be removed to have a $\triangle$-free graph. 

We'll next show how this lemma is used implies testing.

\begin{proof}[of Theorem \ref{thm:test3free}]
 
 Consider a test $T$ which repeats $s$ times the following basic test 

\textbf{Basic test}
\begin{itemize}
\item Pick $u,v, w \in V$ and check if $uvw$ is a triangle. 
\item If so reject. 
\end{itemize}

$T$ accepts after $s$ steps if the basic test has never rejected.

We have to check two things about this test: 

1. If the graph is $\triangle$-free then the test rejects the graph.

If $G$ is $\triangle$-free then $Pr[T \text{ accepts}] = 1$.

2. If the graph is far from $\triangle$-free it rejects with high probability. Note that the test rejects whenever it finds triangles. So we want to show that there are many triangles in graphs that are far from being $\triangle$-free, which is  exactly what the Triangle removal lemma says (Lemma \ref{3removal}.) 

So, if $G$ is $\epsilon$-far from $\triangle$-free then
\[Pr[\text{reject in basic test}] = \frac{\delta(\epsilon)\binom{n}{3}}{\binom{n}{3}} = \delta(\epsilon)\]
using the $\triangle$ removal lemma. 

Thus if we repeat the test $s = \frac{2}{\delta(\epsilon)}$ times then $Pr[T \text{ rejects}] \geq 2/3$. 
\end{proof}

Now where does $\delta(\epsilon)$ come from? From the Szemeredi's regularity lemma we have the constant $M(\epsilon)$ which is approximately $2^{2^{2^{.^{.^{.}}}}},$  a tower of height $poly(1/\epsilon)$. As we will see today, $\delta(\epsilon) \sim \frac{1}{M^3(\epsilon)}$. 

Now let us recall a few things from last lecture.

\begin{lemma}[Szemeredi's Regularity]
For all $\epsilon>0$ there exists $M = M(\epsilon)$ for any graph $G$ with $n$ vertices such that for $n>M$ $G$ has an equipartition into $\{V_1, \ldots, V_k\}$ where $\frac{5}{\epsilon}<k<M(\epsilon)$ such that at least $(1-\epsilon)\binom{k}{2}$ pairs $i$, $j$ are such that $G[V_i, V_j]$ is $\epsilon$-regular. 
\end{lemma}

An equipartition is a partition of the vertices (disjoint collection of sets of vertices whose union is $V(G)$), whose pairwise sizes differ by at most $1$.
Recall that the graph $G[V_i, V_j]$ is a bipartite graph where we remove all the edges within each $V_i$ and $V_j$ and only leave the edges between $V_i$ and $V_j$. 
To be $\epsilon$-regular means that for all $V_i' \subset V_i$ and $V_j' \subset V_j$ such that $|V_i'|> \epsilon|V_i|$ and $|V_j'| > \epsilon|V_j|$ implies that $|d(V_i, V_j) - d(V_i', V_j')| \leq \epsilon$ where $d(V_i, V_j) = \frac{e(V_i, V_j)}{|V_i||V_j|}$. 

So Szemeredi's  regularity lemma says you can partition any graph into a small number of parts (independent of the size of the graph) such that most pairs look "random" enough ($\epsilon$-regularity gives a notion of "pseudorandomness"). 

In order the prove the Triangle removal lemma, we will use the regularity lemma and Komlos-Simonovits lemma from last lecture. Given a regular partition, we want to figure out how to calculate the number of triangles within our graph. We begin by looking at the number of triangles in a random tripartite graph.


Recall from last lecture that  in a  random $3$-partite graph $G$ such that $|V_i| =\frac{n}{3}$ and edges between each $V_i$ show up with probability $\eta$, the $\mathbb{E}[number of \triangle s] = \eta^3(\frac{n}{3})^3$. 


Also recall that if we relax the condition that the tripartite graph was a random graph, to that that it looks pseudorandom (i.e. the pairwise bipartite graphs are $\epsilon$-regular)
and again coumt the number of triangles we showed that this number is almost as large as in the previous, random-graph case.

\begin{lemma}[Komlos-Simonovitz]
Given a tripartite graph $G$ with partitions $A$, $B$, and $C$ such that 
\begin{itemize}
\item $(A,B), (A,C), (B,C)$ are $\eta/2$-regular
\item they are $\eta$-dense
\item $d(A,B), d(A,C), d(B,C) > \eta$
\end{itemize}
then the number of triangles in $G$ is at least $\delta(\eta)|A||B||C|$. 
\end{lemma}

\section*{Proof of the $\triangle$-removal lemma (Lemma \ref{3removal})}
Using all the theorems that we recalled so far we can now prove the $\triangle$-removal lemma.


Let $G$ be an $\epsilon$-far graph. We want to show that the number of triangles in $G$ is $\delta(\epsilon)\binom{n}{3}$. 

The intuition behind the proof is as follows:
\begin{itemize}
\item Use Szemeredi's regularity lemma to obtain an equipartition $V_1,\ldots, V_k$, where $k=k(\epsilon_{sz})$,  and we choose the $\epsilon_{sz}$ from the regularity lemma be $\epsilon_{sz}=\epsilon/8.$
\item Then remove $3$ types of edges:
\begin{itemize}
\item edges within each partition
\item edges between non-regular partitions
\item edges between non-dense partitions
\end{itemize}
\item Lastly we want to make $G$ look like it satisfies the conditions for the Komlos-Simonovitz lemma and count the total number of triangles. 
\end{itemize}

In order to accomplish the second point we define the following: 
\begin{definition}
An edge $(u,v) \in V_i \times V_j$ is \textbf{useful} if it satisfies the following conditions:

1) $i \neq j$

2) $G[V_i, V_j]$ is $\epsilon/8$-regular

3) $G[V_i, V_j]$ is $\epsilon/4$-dense. 
\end{definition}

So, if $G$ is $\epsilon$-far from $\triangle$-freeness let $\epsilon_{sz}=\epsilon/8$.
By Szemeredi's regularity lemma, given $\epsilon_{sz}$ we have an equipartition $V_1, \ldots, V_k$, with $k=k(\epsilon_{sz})=k(\epsilon)$ such that $\frac{40}{\epsilon}< k< M(\epsilon/8)$ such that at least $(1-\epsilon/8)\binom{k}{2}$ pairs $G(V_i, V_j)$ are $\epsilon/8$-regular. 

Now let us assume for the sake of simplicity of presentation that $k \mid n$. We want to count the number of useful edges by bounding the number of non-useful edges. 

1. The number of edges that belong to $V_i$ for all $i$.

Let us fix $i$. Then for $v \in V_i$ it has at most $\frac{n}{k}-1$ neighbors. Therefore the total number of edges inside all $V_i$ is at most $(\frac{n}{k}-1)n$.
Claim: $(\frac{n}{k}-1)n \leq \epsilon/8 \binom{n}{2}$.
By Szemeredi $k > 40/\epsilon$. In particular $k > 16/\epsilon$. Thus
\[\frac{n-k}{k}\leq \epsilon/16(n-1).\]
So 
\[(\frac{n}{k}-1)n \leq \epsilon/8 \frac{n(n-1)}{2} = \epsilon/8 \binom{n}{2}.\]

Thus at most $\epsilon/8\binom{n}{2}$ edges violate the first rule.

2. The total number of edges such that $G[V_i, V_j]$ are not $\epsilon/8$-regular for all $i$ and $j$. 

By Szemeredi's lemma at least $(1-\epsilon/8)\binom{k}{2}$ pairs of $i$ and $j$ are $\epsilon/8$-regular. So at most $\epsilon/8\binom{k}{2}$ are not $\epsilon/8$-regular. 

Now $\left(\frac{n}{k}\right)^2$ is the total number of possible edges between $V_i$ and $V_j$. So we have a total of $\epsilon/8\binom{k}{2}\left(\frac{n}{k}\right)^2$ edges violating rule $2$. 

Claim: $\epsilon/8\binom{k}{2}\left(\frac{n}{k}\right)^2 \leq \epsilon/8\binom{n}{2}$.
We have that 
\[\frac{(k-1)n}{k}\leq n-1\]
so
\[\frac{k(k-1)}{2}\frac{n^2}{k^2} \leq \frac{n(n-1)}{2}.\]

Thus we have at most $\epsilon/8 \binom{n}{2}$ edges violating the second rule. 

3. For all $i$ and $j$ the number of edges such that $G[V_i, V_j]$ is not $\epsilon/4$-dense.

So we have that 
\[d(V_i, V_j) = \frac{e(V_i, V_j)}{|V_i||V_j|}< \epsilon/4.\]
Now using the fact that $|V_i||V_j| =  \left(\frac{n}{k}\right)^2$ we conclude that 
\[e(V_i, V_j) < \epsilon/4 \left(\frac{n}{k}\right)^2.\]
From above we know the right hand side is bounded by $\epsilon/4\binom{n}{2}$. 

Thus we have at most $\epsilon/4\binom{n}{2}$ edges violating the third rule. 

Combining the three results, the total number of edges which are not useful is at most 
\[(\epsilon/8 + \epsilon/8 + \epsilon/4)\binom{n}{2} = \epsilon/2\binom{n}{2}.\]

So now let us return to the proof of the $\triangle$-removal lemma. 

Let $G'$ be the graph obtained from $G$ by removing all non-useful edges (i.e. $G' = G \setminus \{\text{all non-useful edges}\}$.) So in $G'$ we have removed $\epsilon/2\binom{n}{2}$ edges, but since $G$ is $\epsilon$-far, i.e. $\epsilon\binom{n}{2}$ edges need to be removed in order to obtain a triangle free graph, we know there are still triangles in our new graph $G'$. 

\begin{center}
\includegraphics[scale=1]{g4.pdf}
\end{center}


We will count the remaining triangles by observing that $G'$ contains parts $V_i, V_j, V_k$  that satisfy the Komlos-Simonovits lemma. 

\begin{center}
\includegraphics{g1.pdf}
\end{center}


So let $ u\in V_i$, $v \in V_j$, $w \in V_k$ such that $uvw$ is a triangle. Since this triangle is still present after removing the non-useful edges it must be the case that the sets $V_i, V_j$ and $ V_k$ are pairwise $\epsilon/8$-regular and $\epsilon/4$-dense. Then by the Komlos-Simonovitz lemma the number of triangles between $V_i, V_j, V_k$ is $\delta_{ks}|V_i||V_j||V_k| =\delta_{ks}\left(\frac{n}{k}\right)^3$ (where $\delta_{ks}$ is the $\delta$ given by the application of Komlos-Simonovits for $\eta=\epsilon/4.$). Since $k < M(\epsilon)$ we have that in fact the number of triangles is at least 
\[\frac{\delta_{ks}}{M^3(\epsilon)}\binom{n}{3}.\]

This completes the proof of Lemma \ref{3removal}.


We can rephrase the $\triangle$-removal lemma as follows.

1. Suppose $G$ is a dense graph on $n$ vertices such that $G$ has $o(n^3)$ triangles. Then we need to remove $o(n^2)$ edges to get a $\triangle$-free graph.

2. For any $\epsilon$, there exists $\delta(\epsilon)$ such that for all $G$ on $n$ vertices, at least one of the following is true:
\begin{itemize}
\item[1.]$G$ can be made $\triangle$-free by removing at most $\epsilon\binom{n}{2}$ edges.
\item[2.]$G$ has at least $\delta \binom{n}{3}$ triangles.
\end{itemize}

\section*{Other graph properties testable with a constant number of queries}

Now that we have seen that $\triangle$-freeness is testable with a constant number of queries, we can ask the question what are other graph properties which are testable with a constant number of queries (in the dense graph model).

We describe here other examples of testable graph properties. 

1. $\triangle$-freeness, $H$-freeness, bipartiteness

$H$-freeness means given a graph $H$, $G$ does not contain a copy of the graph $H$ as a subgraph. 

These are all \textbf{monotone properties} of a graph, i.e. properties which are preserved under removal of edges and vertices. A paper by Alon and Shapira \footnote{N. Alon and A. Shapira, Every monotone graph-property is testable, Proc. of STOC 2005,
128-137.} gives that all monotone graph properties are testable with a constant number of queries. 

2. Induced $H$-freeness 

This means that given a graph $H$, $G$ does not contain an exact copy of $H$. So if $H$ is the following graph

\begin{center}
\includegraphics[scale=.3]{g2.pdf}
\end{center}

Then $G$ cannot contain any subgraph containing $H$, such as the following

\begin{center}
\includegraphics[scale=.3]{g3.pdf}
\end{center}
This is a \textbf{hereditary property} of a graph, i.e. a property which is preserved under the removal of only vertices (not edges). Alon and Shapira showed that with a $1$-sided error test \footnote{N. Alon and A. Shapira, A characterization of the (natural) graph properties testable with one-sided error. In \textit{Proceedings of the fourty-sixth annual IEEE Symposium on Foundations of Computer Science},
pages 429 - 438. IEEE Computer Society, 2005.}, hereditary properties can be tested with a constant number of queries. 


 A long line of research in this area has culminated with a complete characterization of properties that are testable with a constant number of queries by 2-sided error tests, namely properties that can be reduced to testing a `Szemeredi partition'. \footnote{N. Alon, E. Fischer, I. Newman, and A. Shapira. A combinatorial characterization of the testable graph properties: it’s all about regularity. In \textit{Proceedings of the thirty-eighth annual ACM Symposium on Theory of Computing}, pages 251-260, New York, NY, USA, 2006. ACM Press.}
\footnote{C. Borgs, J. Chayes, L. Lovasz, V. T. Sos, B. Szegedy, and K. Vesztergombi. Graph limits and parameter testing. In Proceedings of the thirty-eighth annual ACM Symposium on Theory of Computing, pages 261–270, New York, NY, USA, 2006. ACM Press.} 

 

\end{document} 
